home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / answrbok / 6_11.lha / 6_11 / 6_11_min.c < prev    next >
Text File  |  1993-08-08  |  6KB  |  180 lines
  1. * Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
  2. * The C++ Answer Book */
  3. * Tony Hansen */
  4. * All rights reserved. */
  5. *
  6.    Subtract u[1..n] - v[1..n] to form w[0..n]
  7.  
  8.    based on
  9.    The Art of Computer Programming, volume 2
  10.    D. Knuth, Section 4.3.1, Algorithm A
  11. /
  12. include <arbint.h>
  13. include <debug.h>    /* DELETE */
  14.  
  15. rbint operator-(const arbint& u, const arbint& v)
  16.  
  17.    int ulen = u.p->length;
  18.    int vlen = v.p->length;
  19.    int wlen = max(ulen, vlen) + 1;
  20.    ARB_type *wv = new ARB_type[wlen];
  21.    ARB_type *uv = u.p->value;
  22.    ARB_type *vv = v.p->value;
  23. f (debug&128)/*DELETE*/    cerr << "operator-\n";
  24. f (debug&128)/*DELETE*/    outputarb(cerr, "\tu=", uv, ulen);
  25. f (debug&128)/*DELETE*/    outputarb(cerr, "\tv=", vv, vlen);
  26. f (debug&128)/*DELETE*/    outputarb(cerr, "\tw(beg)=", wv, wlen);
  27.  
  28.    /*
  29. A1 [Initialize]
  30.     set j <- n
  31.     k <- 0
  32.     { modification: uj for u, vj for v
  33.       k <- 1 }
  34.  
  35. A3(a) [Loop on j]
  36.     decrease j by one
  37.     { modification: decrease uj and vj }
  38.    */
  39. f (debug&128)/*DELETE*/    cerr << "\tbefore first loop, uj=" << (ulen-1) << ", vj=" << (vlen-1) << ", wj=" << (wlen-1) << "\n";
  40.    ARB_Ltype k = 1;
  41.    for (int uj = ulen - 1, vj = vlen - 1,
  42.  wj = wlen - 1;
  43.  uj >= 0 && vj >= 0;
  44.  uj--, vj--, wj-- )
  45. {
  46. /*
  47.     A2(a) [Add digits]
  48.     set w[j] <- (u[j] + v[j] + k) mod b
  49.     { modification: w[wj] <-
  50.       (u[uj] + ~v[vj] + k) mod b }
  51. */dif (debug&128)/*DELETE*/    cerr << "\tin first loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
  52. f (debug&128)/*DELETE*/    cerr << "\t\tuv[" << uj << "]=" << form("%4.4x", uv[uj]) << "\n";
  53. ARB_Ltype t = uv[uj];
  54. f (debug&128)/*DELETE*/    cerr << "\t\tt=" << form("%8.8x", t) << "\n";
  55. f (debug&128)/*DELETE*/    cerr << "\t\tvv[" << vj << "]=" << form("%4.4x", vv[vj]) << "\n";
  56. ARB_type t1 = ~vv[vj];
  57. f (debug&128)/*DELETE*/    cerr << "\t\t~vv[" << vj << "]=" << form("%4.4x", t1) << "\n";
  58. t += t1;
  59. f (debug&128)/*DELETE*/    cerr << "\t\tt=" << form("%8.8x", t) << "\n";d
  60. bug&128)/*DELETE*/    cerr << "\t\tk=" << k << "\n";
  61. t += k;
  62. f (debug&128)/*DELETE*/    cerr << "\t\tt=" << form("%8.8x", t) << "\n";
  63. wv[wj] = t;    // % ARB_based
  64. bug&128)/*DELETE*/    cerr << "\t\twv[" << wj << "]=" << form("%4.4x", wv[wj]) << "\n";
  65.  
  66. /*
  67.     A2(b)
  68.     k <- (u[j] + v[j] + k) / b
  69. */
  70. k = (t / ARB_base) ? 1 : 0;
  71. f (debug&128)/*DELETE*/    cerr << "\t\tk=" << k << "\n";
  72. }
  73. f (debug&128)/*DELETE*/    cerr << "\tafter first loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
  74. f (debug&128)/*DELETE*/    outputarb(cerr, "\tw(now)=", wv, wlen);
  75.  
  76.    /*
  77. NOTE: either (uj >= 0) or (vj >= 0),
  78. but not both. As long as the carry is
  79. non-zero, it must be added to the
  80. next digit.
  81.    */
  82.  
  83.    if (uj >= 0)
  84. {
  85. /*
  86.     Take care of u[1..uj].
  87. */
  88. for ( ; uj >= 0; uj--, wj-- )
  89.     {d        ARB_type t1 = ~0;
  90.     ARB_Ltype t = uv[uj] + t1 + k;
  91.     wv[wj] = t;        // % ARB_mask;
  92.     k = (t / ARB_base ) ? 1 : 0;
  93.     }
  94. f (debug&128)/*DELETE*/    cerr << "\tafter second loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
  95. f (debug&128)/*DELETE*/    outputarb(cerr, "\tw(now)=", wv, wlen);
  96.  
  97. /*
  98.     If there are any digits left
  99.     (there should be at most 1)
  100.     they must be filled with either 0
  101.     or ~0 depending on the sign of wv[wj+1]
  102. */
  103. if (wj >= 0)
  104.     {
  105.     const ARB_type hibit = (ARB_base >> 1);
  106.     const ARB_type rest = ((wv[wj+1] & hibit) != 0) ? ~0 : 0;
  107. f (debug&128)/*DELETE*/    cerr << "\tfinish off, wv[" << (wj+1) << "]=" << form("%4.4x", wv[(wj+1)]) << "\n";dif (debug&128)/*DELETE*/    cerr << "\t\thibit=" << form("%4.4x", hibit) << "\n";d
  108. bug&128)/*DELETE*/    cerr << "\t\twv[wj+1]&hibit=" << ((wv[wj+1] & hibit) != 0) << "\n";
  109. f (debug&128)/*DELETE*/    cerr << "\t\trest=" << form("%4.4x", rest) << "\n";d        do {
  110.     wv[wj--] = rest;
  111.     } while (wj >= 0);
  112.     }
  113. }
  114.  
  115.    else if (vj >= 0)
  116. {
  117. /*
  118.     Take care of v[1..vj]
  119. */d    for ( ; k != 0 && vj >= 0; vj--, wj-- )
  120.     {
  121.     ARB_type t1 = ~vv[vj];
  122.     ARB_Ltype t = k;
  123.     t += t1;
  124.     wv[wj] = t;        // % ARB_based        k = (t / ARB_base) ? 1 : 0;
  125.     }d
  126. bug&128)/*DELETE*/    cerr << "\tafter third loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";dif (debug&128)/*DELETE*/    outputarb(cerr, "\tw(now)=", wv, wlen);
  127.  
  128. /*
  129.     The borrow is now zero, so any
  130.     remaining digits can be negated.
  131. */d    while (vj >= 0)
  132.     wv[wj--] = ~vv[vj--];
  133. f (debug&128)/*DELETE*/    cerr << "\tafter second copy, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
  134. f (debug&128)/*DELETE*/    outputarb(cerr, "\tw(now)=", wv, wlen);
  135.  
  136. /*
  137.     If there are any digits left
  138.     (there should be at most 1)
  139.     they must be filled with either 0
  140.     or ~0 depending on the sign of wv[wj+1]
  141. */
  142. if (wj >= 0)
  143.     {
  144.     const ARB_type hibit = (ARB_base >> 1);
  145.     const ARB_type rest = ((wv[wj+1] & hibit) != 0) ? ~0 : 0;d
  146. bug&128)/*DELETE*/    cerr << "\tfinish off, wv[" << (wj+1) << "]=" << form("%4.4x", wv[(wj+1)]) << "\n";
  147. f (debug&128)/*DELETE*/    cerr << "\t\thibit=" << form("%4.4x", hibit) << "\n";dif (debug&128)/*DELETE*/    cerr << "\t\twv[wj+1]&hibit=" << ((wv[wj+1] & hibit) != 0) << "\n";
  148. f (debug&128)/*DELETE*/    cerr << "\t\trest=" << form("%4.4x", rest) << "\n";d        do {
  149.     wv[wj--] = rest;
  150.     } while (wj >= 0);
  151.     }
  152. }
  153.  
  154.    else
  155. {
  156. /*
  157.     If there is a digit left (there should be at
  158.     most 1), it should be set to k.
  159.     Because we are dealing with 2's complement,
  160.     a carry here means that the number must be
  161.     sign-extended; otherwise the digit is set to 0.
  162.  
  163.     A3(b)
  164.     Set w[0] <- k
  165.     { modification,
  166.       w[0] <- k ? sign(w[wj+1]) ? 0
  167.       }
  168. */d    const ARB_type hibit = (ARB_base >> 1);
  169. const ARB_type rest = ((wv[wj+1] & hibit) != 0) ? ~0 : 0;
  170. f (debug&128)/*DELETE*/    cerr << "\tfinish off, wv[" << (wj+1) << "]=" << form("%4.4x", wv[(wj+1)]) << "\n";dif (debug&128)/*DELETE*/    cerr << "\t\thibit=" << form("%4.4x", hibit) << "\n";dif (debug&128)/*DELETE*/    cerr << "\t\twv[wj+1]&hibit=" << ((wv[wj+1] & hibit) != 0) << "\n";dif (debug&128)/*DELETE*/    cerr << "\t\trest=" << form("%4.4x", rest) << "\n";
  171. while (wj >= 0)
  172.     wv[wj--] = rest;
  173. }
  174.  
  175.    /* Normalize and return */
  176. f (debug&128)/*DELETE*/    outputarb(cerr, "\tw(end)=", wv, wlen);
  177.    arbint w(wv, wlen);
  178.    return w;
  179.  
  180.